package cn.njupt.unionfind;
//对比之下，当前版本并查集写的不是很好
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class UnionFind_ZuoChengYun<E> {
    //child,father
    private Map<Node<E>,Node<E>> fatherMap=new HashMap<>();

    private Map<Node<E>,Integer> sizeMap=new HashMap<>();


    public static class Node<E>{
        E element;
        public Node(E element){
            this.element=element;
        }
    }

    public void makeSet(List<Node<E>> nodes){
        fatherMap.clear();
        sizeMap.clear();
        for (int i = 0; i < nodes.size(); i++) {
            fatherMap.put(nodes.get(i),nodes.get(i));
            sizeMap.put(nodes.get(i),1);
        }
    }

    public void union(Node<E> e1,Node<E> e2){
        if(e1==null || e2==null)return;
        Node<E> ahead=find(e1);
        Node<E> bhead=find(e2);
        int size1= sizeMap.get(e1);
        int size2=sizeMap.get(e2);
        if(ahead!=bhead){
            if(size1<=size2){
                fatherMap.put(ahead,bhead);
                sizeMap.put(bhead,size1+size2);
                sizeMap.remove(ahead);
            }else{
                fatherMap.put(bhead,ahead);
                sizeMap.put(ahead,size1+size2);
                sizeMap.remove(bhead);
            }
        }
    }

    public Node<E> find(Node<E> child){
        Node<E> father=fatherMap.get(child);
        if (child!=father){
            father=find(father);
        }
        fatherMap.put(child,father);
        return father;
    }

    public boolean isSameSet(Node<E> e1,Node<E> e2){
        return find(e1)==find(e2);
    }
}
